#pragma once
#include <iostream>
#include <set>
#include <map>
#include <assert.h>
#include <math.h>
using namespace std;
namespace cc
{
    enum colour
    {
        RED,
        BLACK
    };
    template<class K,class V>
    struct RBtreenode
    {
        colour _col;    
        pair<K,V> _val;
        RBtreenode<K,V> *_left;
        RBtreenode<K,V> *_right;
        RBtreenode<K,V> *_parent;
        RBtreenode(const pair<K,V>& x)
            :_val(x)
            ,_left(nullptr)
            ,_right(nullptr)
            ,_parent(nullptr)
            ,_col(RED)
        {}
    };
    template<class K,class V>
    class RBtree
    {
    public:
        typedef RBtreenode<K,V> node;
        void reor(node *parent)
        {
            node *sub=parent->_left;
            node *subr=sub->_right;
            if(_root==parent)
            {
                _root=sub;
                sub->_parent=nullptr;
                sub->_right=parent;
                parent->_parent=sub;
                parent->_left=subr;
                if(subr)
                    subr->_parent=parent;
            }
            else
            {
                node *pparent=parent->_parent;
                if(pparent->_left==parent)
                    pparent->_left=sub;
                else
                    pparent->_right=sub;
                sub->_parent=pparent;
                sub->_right=parent;
                parent->_parent=sub;
                parent->_left=subr;
                if(subr)
                    subr->_parent=parent;
            }
        }
        void reol(node *parent)
        {
            node *sub=parent->_right;
            node *subl=sub->_left;
            if(_root==parent)
            {
                _root=sub;
                sub->_parent=nullptr;
                sub->_left=parent;
                parent->_parent=sub;
                parent->_right=subl;
                if(subl)
                    subl->_parent=parent;
            }
            else
            {
                node *pparent=parent->_parent;
                if(pparent->_left=parent)
                    pparent->_left=sub;
                else
                    pparent->_right=sub;
                sub->_parent=pparent;
                sub->_left=parent;
                parent->_parent=sub;
                parent->_right=subl;
                if(subl)
                    subl->_parent=parent;
            }
        }
        bool insert(const pair<K,V>& x)
        {
            if(_root==nullptr)
            {
                _root=new node(x);
                _root->_col=BLACK;
                return true;
            }
            node *parent=nullptr;
            node *cur=_root;
            while(cur)
            {
                if(x.first<cur->_val.first)
                {
                    parent=cur;
                    cur=cur->_left;
                }
                else if(x.first>cur->_val.first)
                {
                    parent=cur;
                    cur=cur->_right;
                }
                else
                    return false;
            }
            cur=new node(x);
            if(parent->_val.first>x.first)
                parent->_left=cur;
            else
                parent->_right=cur;
            cur->_parent=parent;
            node *grandfather=parent->_parent;
            while(parent&&parent->_col==RED)
            {
                if(grandfather->_left==parent)
                {
                    node *uncle=grandfather->_right;
                    //情况一：只染色
                    if(uncle&&uncle->_col==RED)
                    {
                        uncle->_col=BLACK;
                        parent->_col=BLACK;
                        grandfather->_col=RED;
                        if(grandfather==_root)
                        {
                            grandfather->_col=BLACK;
                            break;
                        }
                    }
                    //情况二+三：旋转+染色
                    else if(uncle&&uncle->_col==BLACK)
                    {
                        if(parent->_left==cur)
                        {
                            //单旋
                            reor(grandfather);
                            //染色
                            grandfather->_col=RED;
                            parent->_col=BLACK;

                        }
                        else
                        {
                            //双旋
                            reol(parent);
                            reor(grandfather);
                            //染色
                            cur->_col=BLACK;
                            //爷爷节点变红
                            grandfather->_col=RED;
                        }
                        break;
                    }
                    else if(uncle==nullptr)
                    {
                        if(parent->_left==cur)
                        {
                            reor(grandfather);
                            grandfather->_col=RED;
                            parent->_col=BLACK;
                        }
                        else
                        {
                            reol(parent);
                            reor(grandfather);
                            grandfather->_col=RED;
                            cur->_col=BLACK;
                        }
                        break;
                    }
                }
                else
                {
                    node *uncle=grandfather->_left;
                    if(uncle&&uncle->_col==RED)
                    {
                        uncle->_col=BLACK;
                        parent->_col=BLACK;
                        grandfather->_col=RED;
                        if(_root==grandfather)
                        {
                            grandfather->_col=BLACK;
                            break;
                        }
                    }
                    else if(uncle&&uncle->_col==BLACK)
                    {
                        if(parent->_left==cur)
                        {
                            reor(parent);
                            reol(grandfather);
                            grandfather->_col=RED;
                            cur->_col=BLACK;
                        }
                        else
                        {
                            reol(grandfather);
                            grandfather->_col=RED;
                            parent->_col=BLACK;
                        }
                        break;
                    }
                    else if(uncle==nullptr)
                    {
                        if(parent->_left=cur)
                        {
                            reor(parent);
                            reol(grandfather);
                            cur->_col=BLACK;
                            grandfather->_col=RED;
                        }
                        else
                        {
                            reol(grandfather);
                            parent->_col=BLACK;
                            grandfather->_col=RED;
                        }
                        break;
                    }
                }
                cur=grandfather;
                parent=cur->_parent;
                grandfather=parent->_parent;
            }
            return true;
        }
    private:
        node *_root=nullptr;
    };
}